package adt.subsetjava;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
/**
 * The GenerateSubsSets class can be used to generate a power set of one given set. The power set consists in all subsets that could be generated from the initial set.
 * Consider the example below:
 * From a initial SET {1,2,3,4}, the power set that will be generated, not in this order necessarily, is:
 * {{},{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}
 * 
 * @author Carla Sukeyosi, Jessika Renally, Lais Camilo, Tiaraju Smaneoto
 *
 * @version 1.0
 */

public class GenerateSubSetsJava<T> {

	private Set<Set<T>> resultSet = new HashSet<Set<T>>();
	private Stack<T> stack;
	private Set<T> auxSet;
	private Queue<T> queue;
	private Queue<T> auxQueue;

	/**
	 * Generates the power set of one set. This power set consists in all possible subsets which could be
	 * generated from the set.  
	 * @param set the set that will be consider to generate the power set.
	 * @return An set of sets, with size 2^n( n = set's size ), that contains all the possible subsets from the initial set. The power set it is not necessary in order.
	 */
	public Set<Set<T>> subSets(Set<T> set){
		generateSubSets(set);

		return resultSet;
	}

	//this part of the algorithm generate the basic case, all  subsets with 2 elements, if it is possible.
	private void generateBasicSubSet(Set<T> set){
		resultSet.add(new HashSet<T>());
		T[] array=  ((T[]) set.toArray());
		stack = new Stack<T>(); 
		stack.setSize(array.length);
		queue = new LinkedList<T>();

		for(int i=0;i<array.length;i++){
			queue.add(array[i]);
		}

		auxQueue = queueClone();
		for(int i=0;i<array.length;i++){
			stack.push(auxQueue.remove());

			while(!auxQueue.isEmpty()){
				stack.push(auxQueue.remove());
				auxSet=new HashSet<T>();
				T e1 = null;

				e1 = stack.pop();

				if(!e1.equals(stack.peek())){
					auxSet.add(stack.peek());
					auxSet.add(e1);
					if(!(resultSet.contains(auxSet))){
						resultSet.add(auxSet);
					}
				}
			}
			stack.pop();
			auxQueue = queueClone();
		}


	}
	//using the basic subsets formed, this part generates all the possible subsets to complete the power set.
	@SuppressWarnings("unchecked")
	private void generateSubSets(Set<T> set){
		generateBasicSubSet(set);	
		T[] array=  ((T[]) set.toArray());

		Queue<Set<T>> auxQueue = new LinkedList<Set<T>>(); 

		stack = new Stack<T>();
		stack.setSize(array.length);
		queue = (Queue<T>) new LinkedList<T>(); 

		for(int i=0;i < resultSet.size();i++){
			auxQueue.add((Set<T>) resultSet.toArray()[i]);
		}

		while(resultSet.size() < (Math.pow(2, set.size()))){
			for(int i =0 ; i < array.length ; i++){
				queue.add(array[i]);
			}
			Set<T> t = null;
			t = auxQueue.remove(); 

			while(!queue.isEmpty()){
				Set<T> t2 = new HashSet<T>();
				for(int i=0;i<t.size();i++){
					t2.add((T) t.toArray()[i]);
				}

				T element = null;
				element = queue.remove();
				t2.add(element);

				if(!resultSet.contains(t2)){
					resultSet.add(t2);
					auxQueue.add(t2);
				}

			}		
		}
	}
	
	public Queue<T> queueClone(){
		Queue<T> clone = new LinkedList<T>();
		if(!queue.isEmpty()){
			for (int i = 0; i < queue.size(); i++){
				queue.add(queue.peek());
				clone.add(queue.remove());
			}
		}

		return clone;
	}


}
